package com.buddy.learn.algorithm.simple;

import java.util.Arrays;

/**
 * 堆排序
 * 堆是具有以下性质的完全二叉树：
 * 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
 * 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
 *
 * @author Buddy
 * @date 2021/4/20
 */
public class _排序03_堆排序 {

    public static void main(String[] args) {
        int[] arr = {2, 4, 4, 3, 1, 5};
        sortHeap(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sortHeap(int[] arr) {
        // 1. 把无序数组构建成最大堆 leftChild = i * 2 +1，rightChild = i *2 +2
        // 从最后一个非叶子节点开始，依次进行调整
        // 最后一个非叶子结点：2i + 2 = arr.length  -->  i = (arr.length - 2) / 2
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        // 2. 将 堆顶 元素移到末尾
        // 调整堆结构，交换堆顶元素 arr[0] 与 末尾元素 arr[lastIndex]
        for (int lastIndex = arr.length - 1; lastIndex > 0; lastIndex--) {
            //将堆顶元素与末尾元素进行交换
            int temp = arr[0];
            arr[0] = arr[lastIndex];
            arr[lastIndex] = temp;
            //重新对堆进行调整
            adjustHeap(arr, 0, lastIndex);
        }
    }

    /**
     * 下沉调整
     *
     * @param arr    待调整的堆
     * @param index  要下沉的父节点
     * @param length 堆的有效大小
     */
    private static void adjustHeap(int[] arr, int index, int length) {
        int childIndex = 2 * index + 1;
        while (childIndex < length) {
            // 如果有 rightChild，并且 rightChild > leftChild 则指向 rightChild
            if (childIndex + 1 < length && arr[childIndex + 1] > arr[childIndex]) {
                childIndex++;
            }

            // 如果 parent >= 所有的 child 则跳出循环
            if (arr[index] >= arr[childIndex]) {
                break;
            } else {
                // 否则，交换 child 与 parent
                int temp = arr[index];
                arr[index] = arr[childIndex];
                arr[childIndex] = temp;
                // childIndex 向后走
                childIndex = 2 * childIndex + 1;
            }
        }
    }

}
